package th.retrofit.lib;

import java.util.LinkedList;
import java.util.List;

/**
 * https://leetcode-cn.com/problems/path-sum-ii/
 * 给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
 */
public class Solution113 {

    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> results = new LinkedList<>();
        List<Integer> result = new LinkedList<>();
        backtrack(results, result, root, targetSum);
        return results;
    }

    private void backtrack(List<List<Integer>> results, List<Integer> result, TreeNode root, int targetSum) {
        if (root == null) return;
        result.add(root.val);
        targetSum -= root.val;;
        if(root.left == null && root.right == null && targetSum == 0) {
            results.add(new LinkedList<>(result));
        }
        backtrack(results, result, root.left, targetSum);
        backtrack(results, result, root.right, targetSum);
        result.remove(result.size() - 1);
    }

    public static void main(String[] args) {
        TreeNode[] root = new TreeNode[13];
        root[0] = new TreeNode(5);
        root[1] = new TreeNode(4);
        root[2] = new TreeNode(8);
        root[3] = new TreeNode(11);
        root[4] = null;
        root[5] = new TreeNode(13);
        root[6] = new TreeNode(4);
        root[7] = new TreeNode(7);
        root[8] = new TreeNode(2);
        root[9] = null;
        root[10] = null;
        root[11] = new TreeNode(5);
        root[12] = new TreeNode(1);
        TreeNode head = TreeNode.array2Tree(root);
        List<List<Integer>> results = new Solution113().pathSum(head, 22);
        System.out.println(results);
    }

}
